<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
    

    

    



    <meta charset="utf-8">
    
    
    <meta name="sogou_site_verification" content="true">
    
    
    
    <title>缓存淘汰算法-LRU算法 | Lvshen&#39;s Blog | This is My World</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="缓存,LRU">
    <meta name="baidu-site-verification" content="VIVNdSiMZm">
    <meta name="description" content="最近在学习memcache缓存时，发现其s数据淘汰策略都是采用LRU算法进行缓存数据的处理。那么什么是LRU算法，这篇深度好文值得一看。  本文转载至缓存淘汰算法–LRU算法 - 小程故事多 - ITeye博客  1. LRU1.1. 原理LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率">
<meta name="keywords" content="缓存,LRU">
<meta property="og:type" content="article">
<meta property="og:title" content="缓存淘汰算法-LRU算法">
<meta property="og:url" content="https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/index.html">
<meta property="og:site_name" content="Lvshen&#39;s Blog">
<meta property="og:description" content="最近在学习memcache缓存时，发现其s数据淘汰策略都是采用LRU算法进行缓存数据的处理。那么什么是LRU算法，这篇深度好文值得一看。  本文转载至缓存淘汰算法–LRU算法 - 小程故事多 - ITeye博客  1. LRU1.1. 原理LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://my.csdn.net/uploads/201205/24/1337859321_3597.png">
<meta property="og:image" content="http://my.csdn.net/uploads/201205/24/1337859332_7838.png">
<meta property="og:image" content="http://my.csdn.net/uploads/201205/24/1337859339_6844.png">
<meta property="og:image" content="http://my.csdn.net/uploads/201205/24/1337859354_3696.png">
<meta property="og:updated_time" content="2017-09-30T08:01:48.018Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="缓存淘汰算法-LRU算法">
<meta name="twitter:description" content="最近在学习memcache缓存时，发现其s数据淘汰策略都是采用LRU算法进行缓存数据的处理。那么什么是LRU算法，这篇深度好文值得一看。  本文转载至缓存淘汰算法–LRU算法 - 小程故事多 - ITeye博客  1. LRU1.1. 原理LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率">
<meta name="twitter:image" content="http://my.csdn.net/uploads/201205/24/1337859321_3597.png">
    
    <link rel="shortcut icon" href="/img/mylogo.jpg">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/brand.jpg)">
      <div class="brand">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">我的技术小房间</h5>
          <a href="mailto:https://lvshen9.github.io" title="https://lvshen9.github.io" class="mail">https://lvshen9.github.io</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                Archives
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                Tags
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                Categories
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/about"  >
                <i class="icon icon-lg icon-address-book"></i>
                About
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/collection"  >
                <i class="icon icon-lg icon-apple"></i>
                Collection
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://lvshen9.github.io/" target="_blank" >
                <i class="icon icon-lg icon-wordpress"></i>
                Blog
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/lvshen9" target="_blank" >
                <i class="icon icon-lg icon-github-alt"></i>
                GitHub
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">缓存淘汰算法-LRU算法</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">缓存淘汰算法-LRU算法</h1>
        <h5 class="subtitle">
            
                <time datetime="2017-09-30T07:22:13.000Z" itemprop="datePublished" class="page-time">
  2017-09-30
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/技术/">技术</a></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#1-LRU"><span class="post-toc-number">1.</span> <span class="post-toc-text">1. LRU</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#1-1-原理"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">1.1. 原理</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#1-2-实现"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">1.2. 实现</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#1-3-分析"><span class="post-toc-number">1.3.</span> <span class="post-toc-text">1.3. 分析</span></a></li></ol></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#2-LRU-K"><span class="post-toc-number">2.</span> <span class="post-toc-text">2. LRU-K</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#2-1-原理"><span class="post-toc-number">2.1.</span> <span class="post-toc-text">2.1. 原理</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#2-2-实现"><span class="post-toc-number">2.2.</span> <span class="post-toc-text">2.2. 实现</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#2-3-分析"><span class="post-toc-number">2.3.</span> <span class="post-toc-text">2.3. 分析</span></a></li></ol></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#3-Two-queues（2Q）"><span class="post-toc-number">3.</span> <span class="post-toc-text">3. Two queues（2Q）</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#3-1-原理"><span class="post-toc-number">3.1.</span> <span class="post-toc-text">3.1. 原理</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#3-2-实现"><span class="post-toc-number">3.2.</span> <span class="post-toc-text">3.2. 实现</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#3-3-分析"><span class="post-toc-number">3.3.</span> <span class="post-toc-text">3.3. 分析</span></a></li></ol></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#4-Multi-Queue（MQ）"><span class="post-toc-number">4.</span> <span class="post-toc-text">4. Multi Queue（MQ）</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#4-1-原理"><span class="post-toc-number">4.1.</span> <span class="post-toc-text">4.1. 原理</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#4-2-实现"><span class="post-toc-number">4.2.</span> <span class="post-toc-text">4.2. 实现</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#4-3-分析"><span class="post-toc-number">4.3.</span> <span class="post-toc-text">4.3. 分析</span></a></li></ol></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#5-LRU类算法对比"><span class="post-toc-number">5.</span> <span class="post-toc-text">5. LRU类算法对比</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#基于双链表-的LRU实现"><span class="post-toc-number">5.1.</span> <span class="post-toc-text">基于双链表 的LRU实现</span></a></li></ol></li></ol>
        </nav>
    </aside>


<article id="post-缓存淘汰算法-LRU算法"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">缓存淘汰算法-LRU算法</h1>
        <div class="post-meta">
            <time class="post-time" title="2017-09-30 15:22:13" datetime="2017-09-30T07:22:13.000Z"  itemprop="datePublished">2017-09-30</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/技术/">技术</a></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style='display:none'>
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <p>最近在学习memcache缓存时，发现其s数据淘汰策略都是采用LRU算法进行缓存数据的处理。那么什么是LRU算法，这篇深度好文值得一看。</p>
<blockquote>
<p>本文转载至<a href="http://flychao88.iteye.com/blog/1977653" target="_blank" rel="noopener">缓存淘汰算法–LRU算法 - 小程故事多 - ITeye博客</a></p>
</blockquote>
<h4 id="1-LRU"><a href="#1-LRU" class="headerlink" title="1. LRU"></a>1. LRU</h4><h5 id="1-1-原理"><a href="#1-1-原理" class="headerlink" title="1.1. 原理"></a>1.1. 原理</h5><p>LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。</p>
<h5 id="1-2-实现"><a href="#1-2-实现" class="headerlink" title="1.2. 实现"></a>1.2. 实现</h5><p>最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://my.csdn.net/uploads/201205/24/1337859321_3597.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<a id="more"></a>
<ol>
<li>新数据插入到链表头部；</li>
<li>每当缓存命中（即缓存数据被访问），则将数据移到链表头部；</li>
<li>当链表满的时候，将链表尾部的数据丢弃。</li>
</ol>
<h5 id="1-3-分析"><a href="#1-3-分析" class="headerlink" title="1.3. 分析"></a>1.3. 分析</h5><p>【命中率】</p>
<p>当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。</p>
<p>【复杂度】</p>
<p>实现简单。</p>
<p>【代价】</p>
<p>命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。</p>
<h4 id="2-LRU-K"><a href="#2-LRU-K" class="headerlink" title="2. LRU-K"></a>2. LRU-K</h4><h5 id="2-1-原理"><a href="#2-1-原理" class="headerlink" title="2.1. 原理"></a>2.1. 原理</h5><p>LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。</p>
<h5 id="2-2-实现"><a href="#2-2-实现" class="headerlink" title="2.2. 实现"></a>2.2. 实现</h5><p>相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://my.csdn.net/uploads/201205/24/1337859332_7838.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<ol>
<li><p>数据第一次被访问，加入到访问历史列表；</p>
</li>
<li><p>如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；</p>
</li>
<li><p>当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；</p>
</li>
<li><p>缓存数据队列中被再次访问后，重新排序；</p>
</li>
<li><p>需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。</p>
</li>
</ol>
<p>LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。</p>
<h5 id="2-3-分析"><a href="#2-3-分析" class="headerlink" title="2.3. 分析"></a>2.3. 分析</h5><p>【命中率】</p>
<p>LRU-K降低了“缓存污染”带来的问题，命中率比LRU要高。</p>
<p>【复杂度】</p>
<p>LRU-K队列是一个优先级队列，算法复杂度和代价比较高。</p>
<p>【代价】</p>
<p>由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多；当数据量很大的时候，内存消耗会比较可观。</p>
<p>LRU-K需要基于时间进行排序（可以需要淘汰时再排序，也可以即时排序），CPU消耗比LRU要高。</p>
<h4 id="3-Two-queues（2Q）"><a href="#3-Two-queues（2Q）" class="headerlink" title="3. Two queues（2Q）"></a>3. Two queues（2Q）</h4><h5 id="3-1-原理"><a href="#3-1-原理" class="headerlink" title="3.1. 原理"></a>3.1. 原理</h5><p>Two queues（以下使用2Q代替）算法类似于LRU-2，不同点在于2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。</p>
<h5 id="3-2-实现"><a href="#3-2-实现" class="headerlink" title="3.2. 实现"></a>3.2. 实现</h5><p>当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。详细实现如下：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://my.csdn.net/uploads/201205/24/1337859339_6844.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<ol>
<li><p>新访问的数据插入到FIFO队列；</p>
</li>
<li><p>如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；</p>
</li>
<li><p>如果数据在FIFO队列中被再次访问，则将数据移到LRU队列头部；</p>
</li>
<li><p>如果数据在LRU队列再次被访问，则将数据移到LRU队列头部；</p>
</li>
<li><p>LRU队列淘汰末尾的数据。</p>
</li>
</ol>
<blockquote>
<p> 注：上图中FIFO队列比LRU队列短，但并不代表这是算法要求，实际应用中两者比例没有硬性规定。</p>
</blockquote>
<h5 id="3-3-分析"><a href="#3-3-分析" class="headerlink" title="3.3. 分析"></a>3.3. 分析</h5><p>【命中率】</p>
<p>2Q算法的命中率要高于LRU。</p>
<p>【复杂度】</p>
<p>需要两个队列，但两个队列本身都比较简单。</p>
<p>【代价】</p>
<p>FIFO和LRU的代价之和。</p>
<p>2Q算法和LRU-2算法命中率类似，内存消耗也比较接近，但对于最后缓存的数据来说，2Q会减少一次从原始存储读取数据或者计算数据的操作。</p>
<h4 id="4-Multi-Queue（MQ）"><a href="#4-Multi-Queue（MQ）" class="headerlink" title="4. Multi Queue（MQ）"></a>4. Multi Queue（MQ）</h4><h5 id="4-1-原理"><a href="#4-1-原理" class="headerlink" title="4.1. 原理"></a>4.1. 原理</h5><p>MQ算法根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级，其核心思想是：优先缓存访问次数多的数据。</p>
<h5 id="4-2-实现"><a href="#4-2-实现" class="headerlink" title="4.2. 实现"></a>4.2. 实现</h5><p>MQ算法将缓存划分为多个LRU队列，每个队列对应不同的访问优先级。访问优先级是根据访问次数计算出来的，例如</p>
<p>详细的算法结构图如下，<br>$$<br>Q0，Q1….Qk<br>$$<br>代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和引用次数的队列：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://my.csdn.net/uploads/201205/24/1337859354_3696.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>如上图，算法详细描述如下：</p>
<ol>
<li><p>新插入的数据放入Q0；</p>
</li>
<li><p>每个队列按照LRU管理数据；</p>
</li>
<li><p>当数据的访问次数达到一定次数，需要提升优先级时，将数据从当前队列删除，加入到高一级队列的头部；</p>
</li>
<li><p>为了防止高优先级数据永远不被淘汰，当数据在指定的时间里访问没有被访问时，需要降低优先级，将数据从当前队列删除，加入到低一级的队列头部；</p>
</li>
<li><p>需要淘汰数据时，从最低一级队列开始按照LRU淘汰；每个队列淘汰数据时，将数据从缓存中删除，将数据索引加入Q-history头部；</p>
</li>
<li><p>如果数据在Q-history中被重新访问，则重新计算其优先级，移到目标队列的头部；</p>
</li>
<li><p>Q-history按照LRU淘汰数据的索引。</p>
</li>
</ol>
<h5 id="4-3-分析"><a href="#4-3-分析" class="headerlink" title="4.3. 分析"></a>4.3. 分析</h5><p>【命中率】</p>
<p>MQ降低了“缓存污染”带来的问题，命中率比LRU要高。</p>
<p>【复杂度】</p>
<p>MQ需要维护多个队列，且需要维护每个数据的访问时间，复杂度比LRU高。</p>
<p>【代价】</p>
<p>MQ需要记录每个数据的访问时间，需要定时扫描所有队列，代价比LRU要高。</p>
<blockquote>
<p>注：虽然MQ的队列看起来数量比较多，但由于所有队列之和受限于缓存容量的大小，因此这里多个队列长度之和和一个LRU队列是一样的，因此队列扫描性能也相近。</p>
</blockquote>
<h4 id="5-LRU类算法对比"><a href="#5-LRU类算法对比" class="headerlink" title="5. LRU类算法对比"></a>5. LRU类算法对比</h4><p>由于不同的访问模型导致命中率变化较大，此处对比仅基于理论定性分析，不做定量分析。</p>
<table>
<thead>
<tr>
<th>对比点</th>
<th>对比</th>
</tr>
</thead>
<tbody>
<tr>
<td>命中率</td>
<td>LRU-2 &gt; MQ(2) &gt; 2Q &gt; LRU</td>
</tr>
<tr>
<td>复杂度</td>
<td>LRU-2 &gt; MQ(2) &gt; 2Q &gt; LRU</td>
</tr>
<tr>
<td>代价</td>
<td>LRU-2  &gt; MQ(2) &gt; 2Q &gt; LRU</td>
</tr>
</tbody>
</table>
<p>实际应用中需要根据业务的需求和对数据的访问情况进行选择，并不是命中率越高越好。例如：虽然LRU看起来命中率会低一些，且存在”缓存污染“的问题，但由于其简单和代价小，实际应用中反而应用更多。</p>
<p> Java中最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的<code>removeEldestEntry(Map.Entry)</code>方法即可。</p>
<p>如果你去看LinkedHashMap的源码可知，LRU算法是通过双向链表来实现，当某个位置被命中，通过调整链表的指向将该位置调整到头位置，新加入的内容直接放在链表头，如此一来，最近被命中的内容就向链表头移动，需要替换时，链表最后的位置就是最近最少使用的位置。</p>
<h5 id="基于双链表-的LRU实现"><a href="#基于双链表-的LRU实现" class="headerlink" title="基于双链表 的LRU实现"></a>基于双链表 的LRU实现</h5><p>传统意义的LRU算法是为每一个Cache对象设置一个计数器，每次Cache命中则给计数器+1，而Cache用完，需要淘汰旧内容，放置新内容时，就查看所有的计数器，并将最少使用的内容替换掉。 它的弊端很明显，如果Cache的数量少，问题不会很大， 但是如果Cache的空间过大，达到10W或者100W以上，一旦需要淘汰，则需要遍历所有计算器，其性能与资源消耗是巨大的。效率也就非常的慢了。</p>
<p>它的原理： 将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。</p>
<p>这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。</p>
<p>当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。</p>
<p>上面说了这么多的理论， 下面用代码来实现一个LRU策略的缓存。</p>
<p>我们用一个对象来表示Cache，并实现双链表，</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//Java代码  </span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LRUCache</span> </span>&#123;  </span><br><span class="line">   <span class="comment">/** </span></span><br><span class="line"><span class="comment">     * 链表节点 </span></span><br><span class="line"><span class="comment">     * <span class="doctag">@author</span> Administrator </span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     */</span>  </span><br><span class="line">    <span class="class"><span class="keyword">class</span> <span class="title">CacheNode</span> </span>&#123;  </span><br><span class="line">        ……  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> cacheSize;<span class="comment">//缓存大小  </span></span><br><span class="line">    <span class="keyword">private</span> Hashtable nodes;<span class="comment">//缓存容器  </span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> currentSize;<span class="comment">//当前缓存对象数量  </span></span><br><span class="line">    <span class="keyword">private</span> CacheNode first;<span class="comment">//(实现双链表)链表头  </span></span><br><span class="line">    <span class="keyword">private</span> CacheNode last;<span class="comment">//(实现双链表)链表尾  </span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​                    </p>
<p> 下面给出完整的实现，这个类也被Tomcat所使用（ <code>org.apache.tomcat.util.collections.LRUCache</code>），但是在tomcat6.x版本中，已经被弃用，使用另外其他的缓存类来替代它。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LRUCache</span> </span>&#123;</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 链表节点</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> Administrator</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">CacheNode</span> </span>&#123;</span><br><span class="line">	CacheNode prev;<span class="comment">//前一节点</span></span><br><span class="line">	CacheNode next;<span class="comment">//后一节点</span></span><br><span class="line">	Object value;<span class="comment">//值</span></span><br><span class="line">	Object key;<span class="comment">//键</span></span><br><span class="line">	CacheNode() &#123;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">LRUCache</span><span class="params">(<span class="keyword">int</span> i)</span> </span>&#123;</span><br><span class="line">	currentSize = <span class="number">0</span>;</span><br><span class="line">	cacheSize = i;</span><br><span class="line">	nodes = <span class="keyword">new</span> Hashtable(i);<span class="comment">//缓存容器</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 获取缓存中对象</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> Object <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	CacheNode node = (CacheNode) nodes.get(key);</span><br><span class="line">	<span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">		moveToHead(node);</span><br><span class="line">		<span class="keyword">return</span> node.value;</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 添加缓存</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(Object key, Object value)</span> </span>&#123;</span><br><span class="line">	CacheNode node = (CacheNode) nodes.get(key);</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">		<span class="comment">//缓存容器是否已经超过大小.</span></span><br><span class="line">		<span class="keyword">if</span> (currentSize &gt;= cacheSize) &#123;</span><br><span class="line">			<span class="keyword">if</span> (last != <span class="keyword">null</span>)<span class="comment">//将最少使用的删除</span></span><br><span class="line">				nodes.remove(last.key);</span><br><span class="line">			removeLast();</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			currentSize++;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		node = <span class="keyword">new</span> CacheNode();</span><br><span class="line">	&#125;</span><br><span class="line">	node.value = value;</span><br><span class="line">	node.key = key;</span><br><span class="line">	<span class="comment">//将最新使用的节点放到链表头，表示最新使用的.</span></span><br><span class="line">	moveToHead(node);</span><br><span class="line">	nodes.put(key, node);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将缓存删除</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> Object <span class="title">remove</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	CacheNode node = (CacheNode) nodes.get(key);</span><br><span class="line">	<span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span> (node.prev != <span class="keyword">null</span>) &#123;</span><br><span class="line">			node.prev.next = node.next;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (node.next != <span class="keyword">null</span>) &#123;</span><br><span class="line">			node.next.prev = node.prev;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (last == node)</span><br><span class="line">			last = node.prev;</span><br><span class="line">		<span class="keyword">if</span> (first == node)</span><br><span class="line">			first = node.next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">clear</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	first = <span class="keyword">null</span>;</span><br><span class="line">	last = <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 删除链表尾部节点</span></span><br><span class="line"><span class="comment"> *  表示 删除最少使用的缓存对象</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">removeLast</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="comment">//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）</span></span><br><span class="line">	<span class="keyword">if</span> (last != <span class="keyword">null</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span> (last.prev != <span class="keyword">null</span>)</span><br><span class="line">			last.prev.next = <span class="keyword">null</span>;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			first = <span class="keyword">null</span>;</span><br><span class="line">		last = last.prev;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 移动到链表头，表示这个节点是最新使用过的</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> node</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">moveToHead</span><span class="params">(CacheNode node)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (node == first)</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	<span class="keyword">if</span> (node.prev != <span class="keyword">null</span>)</span><br><span class="line">		node.prev.next = node.next;</span><br><span class="line">	<span class="keyword">if</span> (node.next != <span class="keyword">null</span>)</span><br><span class="line">		node.next.prev = node.prev;</span><br><span class="line">	<span class="keyword">if</span> (last == node)</span><br><span class="line">		last = node.prev;</span><br><span class="line">	<span class="keyword">if</span> (first != <span class="keyword">null</span>) &#123;</span><br><span class="line">		node.next = first;</span><br><span class="line">		first.prev = node;</span><br><span class="line">	&#125;</span><br><span class="line">	first = node;</span><br><span class="line">	node.prev = <span class="keyword">null</span>;</span><br><span class="line">	<span class="keyword">if</span> (last == <span class="keyword">null</span>)</span><br><span class="line">		last = first;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> cacheSize;</span><br><span class="line"><span class="keyword">private</span> Hashtable nodes;<span class="comment">//缓存容器</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> currentSize;</span><br><span class="line"><span class="keyword">private</span> CacheNode first;<span class="comment">//链表头</span></span><br><span class="line"><span class="keyword">private</span> CacheNode last;<span class="comment">//链表尾</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>最后欢迎关注我的博客：<a href="https://lvshen9.github.io/" target="_blank" rel="noopener">Lvshen’s Blog</a></p>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2017-09-30T08:01:48.018Z" itemprop="dateUpdated">2017-09-30 16:01:48</time>
</span><br>


        
        原文链接：<a href="/2017/09/30/缓存淘汰算法-LRU算法/" target="_blank" rel="external">https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/</a>
        
    </div>
    
    <footer>
        <a href="https://lvshen9.gitee.io">
            <img src="/img/avatar.jpg" alt="我的技术小房间">
            我的技术小房间
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/LRU/">LRU</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/缓存/">缓存</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/&title=《缓存淘汰算法-LRU算法》 — Lvshen's Blog&pic=https://lvshen9.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/&title=《缓存淘汰算法-LRU算法》 — Lvshen's Blog&source=最近在学习memcache缓存时，发现其s数据淘汰策略都是采用LRU算法进行缓存数据的处理。那么什么是LRU算法，这篇深度好文值得一看。

本文转载至缓存..." data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《缓存淘汰算法-LRU算法》 — Lvshen's Blog&url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/&via=https://lvshen9.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2017/10/04/【算法】快速排序/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">【算法】快速排序</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2017/09/23/JavaScript学习笔记/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">JavaScript学习笔记</h4>
      </a>
    </div>
  
</nav>



    











    <!-- Valine Comments -->
    <div class="comments vcomment" id="comments"></div>
    <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
    <script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
    <!-- Valine Comments script -->
    <script>
        var GUEST_INFO = ['nick','mail','link'];
        var guest_info = 'nick,mail,link'.split(',').filter(function(item){
          return GUEST_INFO.indexOf(item) > -1
        });
        new Valine({
            el: '#comments',
            notify: 'false' == 'true',
            verify: 'false' == 'true',
            appId: "dy9kXHwg5jQUlLryQmpjWRlM-gzGzoHsz",
            appKey: "P9Nh39Ol0JbMMiYqNGHEP3ml",
            avatar: "mm",
            placeholder: "Just go go",
            guest_info: guest_info.length == 0 ? GUEST_INFO : guest_info,
            pageSize: "10"
        })
    </script>
    <!-- Valine Comments end -->







</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        谢谢大爷~
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="https://lvshen9.github.io/blog2/pay/weixin.jpg" alt="打赏二维码">
        </div>
        
        <label class="reward-toggle">
            <input id="rewardToggle" type="checkbox" class="reward-toggle-check"
                data-wechat="https://lvshen9.github.io/blog2/pay/weixin.jpg" data-alipay="https://lvshen9.github.io/blog2/pay/zhifu.jpg">
            <div class="reward-toggle-ctrol">
                <span class="reward-toggle-item wechat">微信</span>
                <span class="reward-toggle-label"></span>
                <span class="reward-toggle-item alipay">支付宝</span>
            </div>
        </label>
        
    </div>
</div>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style='display:none'>
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
            <span>博客内容遵循 <a rel="license" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>我的技术小房间 &copy; 2015 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/&title=《缓存淘汰算法-LRU算法》 — Lvshen's Blog&pic=https://lvshen9.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/&title=《缓存淘汰算法-LRU算法》 — Lvshen's Blog&source=最近在学习memcache缓存时，发现其s数据淘汰策略都是采用LRU算法进行缓存数据的处理。那么什么是LRU算法，这篇深度好文值得一看。

本文转载至缓存..." data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《缓存淘汰算法-LRU算法》 — Lvshen's Blog&url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/&via=https://lvshen9.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="//api.qrserver.com/v1/create-qr-code/?data=https://lvshen9.gitee.io/2017/09/30/缓存淘汰算法-LRU算法/" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '死鬼去哪里了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!又好了!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
